class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        k = k % n;
        int cnt = 0;
        for (int i = 0; i < n; i++){
            int t = nums[i];
            int j = i;
            do{
                j = (j + k) % n;
                swap(t,nums[j]);
                cnt++;
                if (cnt >= n) return;
            }while (j != i);
        }
    }
};